#include<stdio.h>
#include<stdlib.h>
/*
二分查找，只适用于有序
*/
#define pass 
typedef int ElementType;

typedef struct{
    ElementType *elem;//数组基址
    int tableLength;
}SSTable;
SSTable t;//用来测试

int binary_search(SSTable t,ElementType key){
    int l,r;//左右指针,左右指针所指向的元素是不作为比较对象的
    l=0,r=t.tableLength-1;
    int mid;//只比较mid的元素，
    //所以如果开始的时候l或者r就指向的查找的元素，也不会找到，
    //只有找到[mid]=target的时候才会找到
    //当l=r时，因为没有找到elem[mid]!=key下一次循环
    //会导致有一个加一，从而不等，跳出循环
    while(l<=r){
        mid=(l+r)/2;//向下取整
        printf("mid is : %d \n",mid);
        if(t.elem[mid]==key){
            return mid;
        }else if(t.elem[mid]>key){
            r=mid-1;//取左侧
        }else{
            l=mid+1;//取右侧
        }
    }
    return -1;//没有找到
    
}
//在初始化的时候要多初始化一个位置，存放key
void initTable(){
    printf("table length: ");
    scanf("%d",&t.tableLength);
    t.elem=(ElementType*)malloc(sizeof(int) * t.tableLength);
    printf("elemtn value: ");
    for(int i=0;i<t.tableLength;i++){
        scanf("%d",&t.elem[i]);
    }
}
void showTable(){
    printf("init success: ");
    for(int i=0;i<t.tableLength;i++){
        printf("%d ",t.elem[i]);
    }
}

int main(void){
    initTable();
    showTable();
    int key;
    printf("input a key for search:");
    scanf("%d",&key);
    int index=binary_search(t,key);
    printf("index of %d is %d\n",key,index);
    return 0;
}
//12 1 2 3 4 5 6 7 8 9 10 11 12